package Mundo;

import java.util.*;

public class Sortings {
	
	//-----------------------------------------------------------------
    // Atributos
    //-----------------------------------------------------------------

	private ArrayList<Integer> aleatorios;
	
	private ArrayList<Integer> ordenados;
	
	private int[] info;
	
	//-----------------------------------------------------------------
    // Constructores
    //-----------------------------------------------------------------
	
	public Sortings ()
	{
		aleatorios = new ArrayList<Integer>();
		ordenados = new ArrayList<Integer>();
	}

	// -----------------------------------------------------------------
    // Métodos
    // -----------------------------------------------------------------
	
	public void generar (int total)
	{
		aleatorios.clear();
		ordenados.clear();
		
		Random generator = new Random();
		for (int i = 0; i< total; i++)
		{
			int numero = generator.nextInt(10);
			aleatorios.add(numero);
		}
	}
	
	public void hacerOrdenados()
	{
		ordenados.clear();
		for(int i = 0; i < aleatorios.size(); i++)
		{
			int num1 = aleatorios.get(i);
			ordenados.add(num1);
		}
	}
	
		
	public void sort1 (boolean ordenado)
	{
		if(ordenado)
		{
			System.out.println("Arreglo ordenado original: " + ordenados);
			selectionSort(ordenados);
			System.out.println("Arreglo ordenado, luego de sort1: " + ordenados);
		}
		
		else
		{
			System.out.println("Arreglo desordenado" + aleatorios);
			hacerOrdenados();
			selectionSort(ordenados);
			System.out.println("Arreglo ordenado, luego de sort1: " + ordenados);
		}		
	}
	
	public void sort2 (boolean ordenado)
	{
		if(ordenado)
		{
			System.out.println("Arreglo ordenado original: " + ordenados);
			quickSortRecursive(ordenados, 0, ordenados.size()-1);
			System.out.println("Arreglo ordenado, luego de sort2: " + ordenados);
		}

		else
		{
			System.out.println("Arreglo desordenado" + aleatorios);
			hacerOrdenados();
			quickSortRecursive(ordenados, 0, ordenados.size()-1);
			System.out.println("Arreglo ordenado, luego de sort2: " + ordenados);
		}		
	}
	
	// pre: 0 <= i,j < data.length
	// post: data[i] and data[j] are exchanged
	public static void swap(ArrayList data, int i, int j)
	{
		Object temp;
		temp = data.get(i);
		data.set(i, data.get(j));
		data.set(j, temp);
	}		
	
	// pre: 0 <= n <= data.length
	// post: values in data[0..n-1] are in ascending order
	public void selectionSort(ArrayList data)
	{
		int numUnsorted = data.size();
		int index;		// general index
		int max;		// index of largest value
		
		while (numUnsorted > 0)
		{
			// determine maximum value in array
			max = 0;
			for (index = 1; index < numUnsorted; index++)
			{
				int num1 = Integer.parseInt(data.get(max).toString());
				int num2 = Integer.parseInt(data.get(index).toString());
				if (num1 < num2) 
					max = index;
			}
			swap(data,max,numUnsorted-1);
			numUnsorted--;
		}
	}
	
	// pre: left <= right
	// post: data[left] placed in the correct (returned) location
	public int partition(ArrayList<Integer> data, int left, int right)
	{
		while (true)
		{
			// move right "pointer" toward left
			while (left < right && data.get(left) < data.get(right)) 
				right--;
			if (left < right) 
				swap(data,left++,right);
			else 
				return left;
			// move left pointer toward right
			while (left < right && data.get(left) < data.get(right))
				left++;
			if (left < right) 
				swap(data,left,right--);
			else 
				return right;
		}
	}

	// pre: left <= right
	// post: data[left..right] in ascending order
	public void quickSortRecursive(ArrayList<Integer> data,int left,int right)
	{
		int pivot;								// the final location of the leftmost value
	
		if (left >= right) return;
		
		pivot = partition(data,left,right);			/* 1 - place pivot */
		quickSortRecursive(data,left,pivot-1); 		/* 2 - sort small */
		quickSortRecursive(data,pivot+1,right);		/* 3 - sort large */
	}
	
}
